/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec
{
public:
    // Encodes a tree to a single string.
    string serialize(TreeNode *root)
    {
        stringstream s;
        preOrderSerialize(root, s);
        return s.str();
    }

    // Decodes your encoded data to tree.
    TreeNode *deserialize(string data)
    {
        int val;
        stack<TreeNode *> st;
        stringstream ss(data);
        TreeNode head;
        st.push(&head);
        TreeNode *current = &head;
        bool toLeft = false;
        while (true)
        {
            ss >> val;
            if (val == 9999)
            {
                if (toLeft)
                {
                    toLeft = false;
                }
                else
                {
                    st.pop();
                    if (st.empty())
                    {
                        return head.right;
                    }
                    else
                    {
                        current = st.top();
                    }
                }
            }
            else
            {
                if (toLeft)
                {
                    current->left = new TreeNode(val);
                    current = current->left;
                }
                else
                {
                    current->right = new TreeNode(val);
                    current = current->right;
                    st.pop();
                    toLeft = true;
                }
                st.push(current);
            }
        }
        return head.right;
    }

private:
    void preOrderSerialize(TreeNode *tree, stringstream &s)
    {
        if (tree == nullptr)
        {
            // 由于数值范围在±1000以内，所以可以将空节点编码为9999
            // 在解码时就可以直接读取成int
            s << "9999 ";
        }
        else
        {
            s << tree->val << " ";
            preOrderSerialize(tree->left, s);
            preOrderSerialize(tree->right, s);
        }
    }
};

// Your Codec object will be instantiated and called as such:
// Codec ser, deser;
// TreeNode* ans = deser.deserialize(ser.serialize(root));